package oct2013;

/**
 * @author Yinzi Chen
 * @date Nov 14, 2013
 */
public class SearchforaRange {
    public int[] searchRange(int[] A, int target) {
        int l = binarySearch(A, target);
        int r = binarySearch(A, target + 1);
        if (l == A.length || A[l] != target)
            return new int[] { -1, -1 };
        return new int[] { l, r - 1 };
    }

    int binarySearch(int[] A, int target) {
        int n = A.length;
        int l = 0, r = n - 1, m;
        while (l <= r) {
            m = l + r >> 1;
            if (A[m] >= target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}
